Verkle Tries
table: 比較表
Ethereum1.0 Ethereum2.0 Bitcoin
名称 ? Kate(KZG) commitment ?
木構造 merkle patricia tries Verkle tries merkle tries
コミットメント方式 ベクトルコミットメント 多項式コミットメント ベクトルコミットメント
子ノード数 16 16 2
包含証明に必要なプルーフのデータ 15log16(n) log16(n) log2(n)
1.概要
今までのマークルパトリシアツリー(ベクトルコミットメント)ではデータをそのまま保存していたが、Ethereum2.0では多項式コミットメントに移行する議論が起こっている。 これは、多項式を保存し、その値をペアリングで復元することで、参照をより効率的にし、副次的に秘匿化を実現しようとする試みになっている(ぽい）
具体的には、ベクトル内の包含証明がアイテムの亜k図によらず一定サイズになる
アキュムレーターのような機能
これによりステートレスクライアント導入にあたって、ステートの存在証明のサイズを小さな一定サイズにすることができる
現状のツリーベースのコミットをKate commitmentに置き換えることで、ベクトル内の要素の証明をベクトルの長さに依存しない一定サイズのプルーフで証明できるようにする（ぽい)
ちなみに、置き換えた形の木構造をVerkle triesと呼ぶ。
つまり、patricia merkle tries→Verkle triesが議論の対象
ステートレスクライアントというアイディアがある。全ステートに対する暗号学的なコミットメントが、Ethereumのブロックヘッダーにステートルートという形で記録されている。ブロックの提供者に各トランザクションがアクセスするステート自体とそれが有効なステートであることの証明をセットで提供してもらうことで、ノードがそのストレージにステートを保持しなくて済むようにしようというもの。
2.今までのEthereum
2.1 merkle patricia triesの形
https://scrapbox.io/files/60ec1d7f99932200202e8550.png
https://scrapbox.io/files/60ec1b119df1b1001ca96efd.png
- 新しいルートハッシュ（コミットメント）に到達するために、ブロックごとに挿入／更新されていく
- 検証者がブロックごとに（あるいはトランザクションごとに）検査し、証明する。
サイズNのリーフを持つ大規模なd-ary木がある場合、リーフが変更されると、新しい状態を反映した新しいルートを計算するために、O(log-d(N))個のノードの更新（ルートまで）が必要
これには、時間的にも（ライトクライアントにサービスを提供する場合は空間的にも）証人として[* (d-1)*O(log-d(N))個の兄弟ノードのハッシュ/コミットが追加で必要
m<<Nの場合、m個のランダムなリーフの更新を一括して行うブロックでは、ごく一部のノードが証人や計算を共有することになるため、更新オーダーは更新ごとにあまり変わらない
2.2merkle patricia triesの包含証明
各ノードが最大16個の子ノードのハッシュを持っている。そのため、単一アイテムの包含証明にはツリーのルートからそのアイテムがあるリーフノードまでのツリーの経路上のノードデータがプルーフとして必要になる。
この経路上のノードデータのうち、関係する子ノード以外の兄弟ノードのハッシュ値になるので15個のハッシュがあればリーフノードのデータから各ノードのハッシュを計算し、上位ノードの兄弟ノードのハッシュ値（プルーフ）を計算しながらツリーをたどり、ルートノードの子ノードのハッシュ値と合致すればアイテムがツリーに包含されていることを検証できる。
ステートレスクライアントのようなアプローチをする場合、現状のmerkle patricia tries ではひとつのプルーフあたり
15 log_16(n)個のデータが必要になる(nはツリー上の総データ数)
例えば、高さ2のmerkle patricia tries で全てのノードにリーフがついている場合、データ数は16^2個なので、一つのプルーフを作成するには$ 15log_{16}16^2=15*2=30個のデータが必要になる
2.3 ステートのサイズについて
ステートレスイーサリアムの実験では、1MBのブロックプルーフサイズが観察され（その大部分はマークルプルーフでした）、攻撃時に複数回爆発することさえありました。
https://scrapbox.io/files/60efb6efb1b7c0001c745c63.png
Block proofs-kBytes
これを回避する1つの方法は、画像からdを取り除くバイナリマークルツリーですが、ツリーの深さは増加しますが、それでもO log（N）のままです。
これを回避する方法の一つとして、dを画像から取り除いたバイナリメルクルツリーがありますが、その場合、ツリーの深さは増加しますが、それでもO log(N)のままです。
https://scrapbox.io/files/60efb74b408f55001d12613f.png
青：hex witness
燈：binary witness
3.Kate Commitmentsの場合
- ブロックヘッダに容易に収まる小さなサイズ（48バイト）でありながら、強固なセキュリティ保証を実現。
- コミットメントがチャンク化されたデータのサブセットを使用して作成されたことを容易に証明可能
- 非常に小さく、理想的には一定の証明サイズ状態を追跡するためには、(index=>value map)をインクリメンタルに変更することが容易でなければならない。
実際には、秘密の(固定)値sでの多項式$ f(x) の評価が楕円曲線で表現される。つまり、$ [f(s)]=f([s]) であり、$ [s],[s^2],...[s^d] を生成するためには、Trusted Setupが必要になる
$ x^iがあればどこでも多項式に接続できる
3.1KZG CommitmentをVector Commitmentとして使用する
KZG Commitmentの主な機能は楕円曲線グループの要素$ C=[f(s)] を介して多項式$ f(x) をコミットすること
ベクトルコミットメントはinput として$ dと異なる値$ v_0,v_1,...,v_{d-1} をとり、これらの値のいずれかで検証が可能なコミットメント$ Cを生成する
例えば、マークルツリーはベクトルコミットメントであり$ i番目の値で開く要素は$ log {d}のハッシュ値（proof) を必要とすることになる。
ここで、$ ωを$ d番目のroot of unity とする。すなわち、$ ω^d = 1, ω^i ≠ 1 for 0 ≦ i ≦ d
Kate commitmentを$ d-1次の多項式$ f(x)のコミットにすることで長さ$ dのベクトルへコミットするvecor commitmentに変更することができる。
この$ d-1 次の多項式$ f(x)は以下のように定義される。
$ f(ω^i)=v_i for 0≦i<d
任意の点$ iにおけるコミットメント$ Cを公開することで、kate proofをシンプルに計算することができるうえ
幸運なことに、このproofは一定のサイズなので幅$ dに依存することがない。
さらに、多くのこのようなproofs はsingle proofに結合されますが、これは証明が安っぽくなります。
3.2Verkle Triesの紹介
各ノードはマークルツリーと違い、dノードのハッシュではなくベクトルコミットメントを使ってdノードをコミットする
マークルツリーの場合はd=2
従来のd-array Merkle treeは非効率的だった
各proofは各証明にリーフへのパス上の各ノードのアクセスされていない兄弟姉妹をすべて含める必要がある
1つのproof生成に$ (d-1)log_dn=(d-1){log_n}/{log_d}のハッシュが必要なので binary Merkle treeよりも非効率
binary Merkle treeだと、$ lognのハッシュのみでよい
これは、ハッシュ関数がベクトルコミットメントに適していないから。証明には、すべての兄弟が与えられる必要がある
KZG多項式コミットメント・スキームをベクトル・コミットメントとして使用することにより、各レベルは一定のサイズ(48byte)の証明しか必要としないため、 d-aryのMerkle木を殺すd-1という厄介な要因は消える
verkle trieとは，内側のノードが子へのd-aryベクトルのコミットであり，i番目の子が接頭辞$ iをd桁の2進数で持つすべてのノードを含むtrieである．
例として，次のようにd = 16 verkle trieに9個のノードが挿入されているとする
https://scrapbox.io/files/60ee8778d177730022f57961.png
リーフノードのルートは、単純に32バイト文字列の（Key,Value）ペアのハッシュであり、インナーノードのルートは、ベクトルのコミットメントのハッシュ（KZGでは$ G_1の要素)
3.3一枚の葉のバークルプルーフ
ここでは、KeyとValueが既知であると仮定する（どのようなウィットネス方式でも提供されなければならない）。
そして、key pathが交差する各インナーノードに対して、そのノードに対するコミットメントをproofに追加しなければならない
例えば、上の例でリーフ0101 0111 1010 1111 -> 1213を証明したいとすると（緑のとこ）、パスが通過するノードAとノードB（シアンのとこ）にコミットメントを与えなければなりません。
ルート自体は検証者に知られているので、与える必要はない
ルートとノード自体は緑でマークされているが、これは証明に必要なデータであり、すでに与えられていると仮定しているため、証明の一部ではない
次に、各インナーノードのKZG証明を追加する必要がある。これは、子ノードのハッシュがKZGコミットメントを正しく表していることを証明するもの。つまり、この例におけるproofは、以下の3つのKZG評価証明で構成されることになる。
ノード0101 0111 1010 1111 -> 1213のルート（キーと値のハッシュ）が，インデックス1010におけるインナーノードBのコミットメントの評価であることの証明
インナーノードBのルート（KZGコミットメントのハッシュ）が，インデックス0111におけるインナーノードAのコミットメントの評価であることの証明
インナーノードAのルート（KZGコミットメントのハッシュ）がインデックス0101におけるルートのコミットメントの評価であることの証明
完全な証明は、$ log_d{(n-1)}個の楕円曲線群要素と、明らかにするための追加の$ log_d{n}個の群要素で構成されることになる。
ルートは常に知られており、証明に含める必要がないため、n-1になっている
ここまで見ると、各レベルでKateの証明を追加する必要があるように見えるが、幸いなことに実際はそのようなことはない.
KZGの証明は、さまざまな方式で小さな一定のサイズに圧縮することができるので、任意の数のインナーノードがあれば、小さなバイト数で証明を行うことができるうえ、証明すべき葉がいくつあっても、それらをまとめて証明するためには、小さなサイズの証明しか必要ない。
つまり、償却コストは、インナーノードのコミットの合計サイズだけ
実際には、計算と検証が非常に効率的なスキームが必要なので、このスキームを使用している。 サイズは合計128バイトとかなり小さい
3.3Verkle trieの深さ(depth)の平均
平均深度（パス上の内側のノードの数）を持つバークルツリーの n 個のランダムな鍵が挿入されたバークルツリーの平均的な深さ（パスの内部ノード数）は $ log_d{n}+2/3 と言われている(Dankrad Feist氏調べ)
例えば、要素数$ n = 2^{30} $ d=2^{10}のとき、平均深度は3.67になる
3.4Attack verkle trie depth
攻撃者は、証明経路を長くするために、攻撃された鍵の兄弟ノードを埋めようとすることができる。
証明サイズを最大化するためには、1レベルにつき1つの鍵を挿入すればよいが、そのためにはハッシュプレフィックスの衝突を見つけられなければならない。
現在、80ビットまでのプレフィックスコリジョンが発見されており、$ d=2^{10}の場合、最大で8レベルの衝突を引き起こすことができる。これは、$ n=2^{30}の鍵に対して予想される平均的な深さに比べて約2倍の長さでしかなく、この攻撃は全体的にあまり効果がない
具体的な方法